//
//  47_全排列2.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/14.
/**
 https://leetcode.cn/problems/permutations-ii/
 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 示例 1：

 输入：nums = [1,1,2]
 输出：
 [[1,1,2],
  [1,2,1],
  [2,1,1]]
 示例 2：

 输入：nums = [1,2,3]
 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 */

import UIKit

class TowQuanPailie: NSObject {
    func QA() {
        print(permuteUnique([1,1,2]))
//        print(permuteUnique([1,2,3]))
        
    }
    func permuteUnique(_ nums: [Int]) -> [[Int]] {
        if nums.count == 0 { return [] }
        var results = [[Int]]()
        dps(0, nums, &results)
        return results
    }
    
    func dps(_ index: Int, _ nums: [Int], _ resluts: inout [[Int]]) {
        if index == nums.count {
            resluts.append(nums)
            return
        }
        
        for i in index..<nums.count {
            if isRepate(nums, i, index) {
                continue
            }
            var tempArray = nums
            (tempArray[i], tempArray[index]) = (tempArray[index], tempArray[i])
            dps(index + 1, tempArray, &resluts)
        }
    }
    
    func isRepate(_ nums: [Int], _ i: Int, _ index: Int) -> Bool {
        for j in index..<i {
            if nums[j] == nums[i] { return true }
        }
        return false
    }
}
